package main

import (
	"fmt"
	"math/rand"
	"time"
)

func merge(left, right []int) (ret []int) {
	for len(left) != 0 && len(right) != 0 {
		if left[0] <= right[0] {
			ret = append(ret, left[0])
			left = left[1:]
		} else {
			ret = append(ret, right[0])
			right = right[1:]
		}
	}
	for len(left) != 0 {
		ret = append(ret, left[0])
		left = left[1:]
	}
	for len(right) != 0 {
		ret = append(ret, right[0])
		right = right[1:]
	}
	return
}
func mergeSort(arr []int) []int {
	length := len(arr)
	if length < 2 {
		return arr
	}
	middle := length / 2
	left := arr[:middle]
	right := arr[middle:]
	return merge(mergeSort(left), mergeSort(right))
}

func main() {
	arr := make([]int, 100)
	rand.Seed(time.Now().UnixNano())

	length := len(arr)
	for i := 0; i < length; i++ {
		arr[i] = rand.Intn(1000)
	}
	fmt.Println(arr)
	fmt.Println(mergeSort(arr))
}
